package test.Sorting;

import java.util.Arrays;

//冒泡排序
public class Sort {

    //1.冒泡排序
    public static void bubblingSort(Comparable[] a){
        for (int i = a.length-1;i>0;i--){
            for (int j = 0;j<i;j++){
                if (Util.greater(a[j],a[j+1])){
                    Util.exchange(a,j,j+1);
                }
            }
        }
    }

    //2.选择排序
    public static void selectSort(Comparable[] a){
        for (int i= a.length;i>0;i--){
            int minIndex = a.length-i;
            for (int j=a.length-i;j<a.length;j++){
                if (Util.greater(a[minIndex],a[j])){
                    minIndex = j;
                }
            }
            Util.exchange(a,minIndex, a.length-i);
        }
    }
    //3.插入排序
    public static void injectSort(Comparable[] a){
        for (int i = 0;i<a.length-1;i++){
            for (int j = i+1;j>=1;j--){
                if(Util.greater(a[j-1],a[j])){
                    Util.exchange(a,j-1,j);
                }
            }
        }
    }
    //4.希尔排序
    public static void hillSort(Comparable[] a){
        int length = a.length;
        int h = length;
        while (h>=1){
            for (int i=0;i<=length-1-h;i++){
                if(Util.greater(a[i],a[i+h])){
                    Util.exchange(a,i,i+h);
                }
            }
            h = h/2;
        }
    }

    public static void main(String[] args) {
        Integer[] arr = {1,-1,3,9,-85,8,4,6,100,50};
//        bubblingSort(arr);
//        selectSort(arr);
//        injectSort(arr);
        hillSort(arr);
        System.out.println("arr = " + Arrays.toString(arr));
    }
}
